Ngày 11 tháng 11 năm 1998, Rudd đọc bài diễn văn đầu tiên của mình tại Quốc hội Úc.[23] Nhằm phản đối kế hoạch lập một phi đạo song song ở Phi trường Brisbane, Rudd tổ chức thành công một trong những cuộc tuần hành lớn nhất ở Brisbane, gây chú ý cho các phương tiện truyền thông.

Bộ trưởng Ngoại giao Nội các Đối lập (2001 – 2005)

Sau thành công trong kỳ tuyển cử năm 1998, Rudd trở thành phát ngôn nhân cho phe đối lập tại Quốc hội, rồi được bổ nhiệm vào chức vụ Bộ trưởng Ngoại giao cho Nội các Đối lập sau kỳ bầu cử năm 2001. Rudd chỉ trích kịch liệt chủ trương của chính phủ Howard ủng hộ Hoa Kỳ trong chiến tranh Iraq năm 2003, trong khi tiếp tục duy trì quan điểm ủng hộ liên minh Úc-Mỹ.

Kinh nghiệm và các hoạt động nghị trường của Rudd trong lúc diễn ra chiến tranh Iraq khiến ông trở nên nhân vật nổi tiếng nhất trong giới lãnh đạo đảng Lao động ở Quốc hội. Khi lãnh tụ phe đối lập Simon Crean bị người tiền nhiệm Kim Beazley thách thức vào tháng 6, Rudd không chịu công khai ủng hộ ai.[24] Đến lúc Crean chấp nhận từ chức trong tháng 11, Rudd được xem là ứng cử viên triển vọng cho vị trí lãnh đạo đảng.[25] Tuy nhiên, ông tuyên bố ủng hộ Kim Beazley.

Sau khi Mark Latham đắc cử vào vị trí lãnh đạo đảng, nhiều người chờ xem Rudd bị thất sủng do đã ủng hộ Beazley, nhưng ông vẫn duy trì được ảnh hưởng của mình. Tuy nhiên, mối quan hệ giữa hai người ngày càng xấu đi, nhất là khi Latham hứa sẽ rút quân khỏi Iraq vào Giáng sinh năm 2004 mà không hỏi ý kiến Rudd.[26] Sau khi Latham thất bại trong kỳ bầu cử liên bang vào tháng 10 năm 2004, Rudd lại được nhắc đến như một ứng viên triển vọng cho chức lãnh tụ đảng. Lần này, Rudd lại từ chối thách thức Latham mà muốn duy trì vai trò bộ trưởng ngoại giao cho nội các đối lập.

Tháng 1 năm 2005, Latham đột ngột từ chức khi Rudd đang thăm Indonesia. Ông từ chối phát biểu về việc kế nhiệm lãnh tụ đảng[27] do ông không muốn đối đầu với Beazley. Ông nói, "Công việc quan trọng nhất đối với tôi lúc này là cố vấn cho các đồng nghiệp của tôi trong đảng".[28] Sau khi về nước, Rudd hội ý với các nghị sĩ thuộc đảng Lao động ở Sydney và Melbourne, rồi tuyên bố không tranh chức lãnh tụ đảng. Kim Beazley đắc cử vào vị trí này.

Tháng 6 năm 2005, ngoài chức trách Bộ trưởng Ngoại giao và An ninh Quốc tế trong Nội các Đối lập, Rudd đảm trách thêm nhiệm vụ của Bộ trưởng Thương mại.